/**
 * Created with IntelliJ IDEA.
 * Description:KMP算法
 * User: xwl
 * Date: 2023-04-03
 * Time: 12:10
 */

public class KMP {
    public static void main(String[] args) {
        //创建目的数组
        char[] dest = {'A','B','A','B','C'};
        //创建源数组
        char[] source = {'A','B','A','B','A','B','C','A','A'};
        //创建一个空数组接受NEXT数组
        int[] next = new int[dest.length];
        //调用函数
        buildNext(dest,next);
        int ret = KMP(dest,source,next);
        //输出
        for (int x: next) {
            System.out.print(x+" ");
        }
        System.out.println();
        if(ret == 0) {
            System.out.println("未找到目标");
        }else {
            for (int i = ret; i < ret + dest.length; i++) {
                System.out.print(source[i]+" ");
            }
        }
    }
    //KMP算法
    public static int KMP(char[] dest, char[] source, int[] next) {
        //分别用来遍历dest数组和source数组
        int i = 0;
        int j = 0;
        //循环匹配
        while( i < source.length) {
            if(j < dest.length && source[i] == dest[j]) {
                i++;
                j++;
            }else if(j > 0) {
                j = next[j-1];
            }else {
                i++;
            }
            //如果匹配成功返回dest数组首元素下标
            if(j == dest.length) {
                return i - j;
            }
        }
        return 0;
    }
    //创建NEXT数组
    public static void buildNext(char[] dest, int[] next) {
        //定义一个共同前后缀长度
        int flag = 0;
        //创建一个用于循环的初始量
        int i = 1;
        //实现NEXT数组
        while(i < dest.length) {
            //
            if(dest[i] == dest[flag]) {
                flag++;
                next[i] = flag;
                i++;
            }else {
                if(flag == 0) {
                    next[i] = 0;
                    i++;
                }else {
                    flag = next[flag - 1];
                }
            }
        }
    }
}
